XML documents are increasingly used in today's applications for storing and exchanging data. The data in those XML documents is retrieved, updated and inserted. XML documents have their own structure, determined by a Document Type Definition (DTD) \cite{2006xml} or some other form of XML schema (eg. \cite{2001xsd}). Arenas and Libkin looked for an analogon to BCNF in the XML context \cite{2004arenas}. As a summary they answered the following questions:

\begin{itemize}
    \item[(1)] What is a redundancy and an update anomaly in XML?
    \item[(2)] What do functional dependencies in XML look like?
    \item[(3)] What are ``bad'' functional dependencies?    
    \item[(4)] Is there an algorithm to convert an arbitrary DTD into one without ``bad'' functional dependencies?
\end{itemize}

\noindent This chapter summarizes the answers to questions (1)-(3), given in the publications of Arenas and Libkin  \cite{2002arenas, 2003arenas, 2004arenas, 2006arenas}. Section~\ref{sec:xml_pre} introduces the XML document and schema model. We then show how to map relational data to XML documents and DTDs in Section~\ref{sec:xml_map}. Section~\ref{sec:xml_fd} defines XML functional dependencies (XFD) and finally, Section~\ref{sec:xml_nf} introduces XML Normal Form.


\begin{paragraph}{XML Documents.} An XML document is hierarchically structured and built of elements. An element contains a string or a sequence of further elements. Elements start with a \textit{start-tag}, e.g. \texttt{<course>}, and end with an \textit{end-tag}, e.g. \texttt{</course>}. Elements might also include attributes given in the start-tag, e.g. the attribute \texttt{type} in the element \texttt{course} (\texttt{<course type='VO'>}). The top element of a document is called the \textit{document} or \textit{root} element. An XML document with the same information as in Figure~\ref{fig:relCourse} is given in the next example.

\begin{example}
\label{ex:course_xml}
\begin{figure}[t]
\begin{lstlisting}[language=XML]
<courses>
   <course type="VO">
      <lecture>Algebra I</lecture>
      <room building="Main">HS1</room>
   </course>
   <course type="UE">
      <lecture>Algebra I</lecture>
      <room building="Dep">SEM1</room>
   </course>
   <course type="UE">
      <lecture>Economics</lecture>
      <room building="Dep">SEM1</room>
   </course>
</courses> 
\end{lstlisting}
\caption{An XML document with the same information as in Figure~\ref{fig:relCourse}.}
\label{fig:xmlCourse}
\end{figure}

The root element of the document in Figure~\ref{fig:xmlCourse} is \texttt{courses}, which stores several \texttt{course} elements. Each \texttt{course} element has as attribute a course \texttt{type}. The name of the course is stored in a \texttt{lecture} element, and its location in a \texttt{room} element. The \texttt{room} element has a \texttt{building} attribute.
\end{example}
\end{paragraph}

\begin{paragraph}{Document Type Definitions (DTDs).} A schema of an XML document defines the allowed trees. This structure is defined using a schema language, which is most often given by a DTD (defined in \cite{2006xml}) or an XML Schema (XSD) \cite{2001xsd}. In the following we focus on DTDs as a schema language. The next example gives a possible schema to the XML document in Figure~\ref{fig:xmlCourse}

\begin{example}
\label{ex:dtdCourse}

The DTD given in Figure~\ref{fig:dtdCourse} allows for XML documents with the root element \texttt{courses}. Each \texttt{course} element has zero or more \texttt{course} child elements. Each \texttt{course} element has a child of type \texttt{lecture} and \texttt{room}. Additionally, the \texttt{course} element has a required attribute \texttt{type}. The \texttt{lecture} and \texttt{room} elements contain strings (\texttt{\#PCDATA}). The \texttt{room} element has a \texttt{building} attribute.
\end{example}

\begin{figure}[t]
\centering\begin{lstlisting}[language=DTD]
<!DOCTYPE courses [
  <!ELEMENT courses (course*)>
  <!ELEMENT course (lecture, room)>
  <!ATTLIST course
         type CDATA #REQUIRED>
  <!ELEMENT lecture (#PCDATA)>
  <!ELEMENT room (#PCDATA)>
  <!ATTLIST room
         building CDATA #REQUIRED>
]>
\end{lstlisting}
\caption{A DTD representing courses}
\label{fig:dtdCourse}
\end{figure}
\end{paragraph}
  
\begin{section}{Preliminaries}
\label{sec:xml_pre}

In this section we formally introduce XML documents. For XML documents and DTDs we use the same formal model  as in \cite{2006arenas2} originally introduced by Fan and Libkin \cite{2001fanlibkin, 2002fanlibkin}. We have the following disjoint sets: $\mathit{El}$ representing element names, $\mathit{Att}$ attribute names, $\mathit{Str}$ possible values of string-valued attributes, and $\mathit{Vert}$ node identifiers. We assume that all attribute names $\mathit{Att}$ start with the symbol $@$ (an no others are starting with $@$). The symbols $\tS$ and $\bot$ are not part of the previous sets. An XML document can be represented as a tree, formalized as follows. Notice that we do not allow mixed content in XML trees.
   
   \begin{definition}{(XML tree $T$ \cite{2004arenas})} An XML tree $T$ is defined to be a tree $(V, lab, ele, att, root)$, where
    \begin{itemize}
     \item $V \subseteq \mathit{Vert}$ is a finite set of \textit{vertices (nodes)}.
     \item $lab$ \ldots $V \ra El$, is a function that assigns element types to vertices.
     \item $ele$ \ldots $V \ra Str \cup V^*$, is a function that assigns to vertices its child vertices, which is either an ordered set of vertices or a string.
     \item $att$ \ldots a partial function $V \times Att \ra Str$, such that for each $v \in V$, the set $\{ @l \in Att \mid att(v, @l) \mbox{ is defined } \}$ is finite.
     \item $root \in V$ is called the \textit{root} of $T$
    \end{itemize}
    
    \noindent The parent-child edge relation on $V$, $\{\left(v_1,v_2\right) \in V \times V \mid v_2 \mbox{ occurs in } \ffo{ele}\left( v_1 \right) \}$, is required to form a rooted tree.
   \end{definition}
   
\begin{example}
The XML document in Figure~\ref{fig:xmlCourse} is represented by the XML tree in Figure~\ref{fig:treeCourse}. This tree contains a set of nodes $V = \{ v_i \mid i \in \left[ 0, 9 \right] \}$. The nodes are of the following element types:
\begin{align*}
 \ffo{lab}\left(v_0\right) &= \texttt{courses} & \ffo{lab}\left(v_1\right) &= \texttt{course} & \ffo{lab}\left(v_2\right) &= \texttt{lecture} \\
 \ffo{lab}\left(v_3\right) &= \texttt{room} & \ffo{lab}\left(v_4\right) &= \texttt{course} & \ffo{lab}\left(v_5\right) &= \texttt{lecture} \\
 \ffo{lab}\left(v_6\right) &= \texttt{room} & \ffo{lab}\left(v_7\right) &= \texttt{course} & \ffo{lab}\left(v_8\right) &= \texttt{lecture} \\
 \ffo{lab}\left(v_9\right) &= \texttt{room}.
\end{align*}
\noindent $\ffo{ele}$ assigns to all nodes its children:
\begin{align*}
 \ffo{ele}\left(v_0\right) &= \left[ v_1, v_4, v_7\right] & \ffo{ele}\left(v_1\right) &= \left[v_2, v_3\right] & \ffo{ele}\left(v_2\right) &= \textnormal{``Algebra I''} \\
 \ffo{ele}\left(v_3\right) &= \textnormal{``HS1''} & \ffo{ele}\left(v_4\right) &= \left[v_5, v_6\right] & \ffo{ele}\left(v_5\right) &= \textnormal{``Algebra I''} \\
 \ffo{ele}\left(v_6\right) &= \textnormal{``SEM1''} & \ffo{ele}\left(v_7\right) &= \left[v_8, v_9\right] & \ffo{ele}\left(v_8\right) &= \textnormal{``Economics''} \\
 \ffo{ele}\left(v_9\right) &= \textnormal{``SEM1''}.
\end{align*}
\noindent The attributes in $T$ are the following:
\begin{align*}
 \ffo{att}\left(v_1,\texttt{@type}\right) &= \textnormal{``VO''} & \ffo{att}\left(v_3,\texttt{@building}\right) &= \textnormal{``Main''} \\
 \ffo{att}\left(v_4,\texttt{@type}\right) &= \textnormal{``UE''} & \ffo{att}\left(v_6,\texttt{@building}\right) &= \textnormal{``SEM1''} \\
 \ffo{att}\left(v_7,\texttt{@type}\right) &= \textnormal{``UE''} & \ffo{att}\left(v_9,\texttt{@building}\right) &= \textnormal{``SEM1''}.
\end{align*}
\noindent Moreover, the $root$ of the tree $T$ is $v_0$.
\end{example}

\begin{sidewaysfigure}[htbp]
\centering\begin{tikzpicture}[level distance=12mm,
                       level 1/.style={sibling distance=65mm},
                       level 2/.style={sibling distance=24mm},
                       level 3/.style={sibling distance=15mm},
                       level 4/.style={sibling distance=10mm},
                       edge from parent path={(\tikzparentnode.south) -- (\tikzchildnode.north)}]
      \tikzstyle{every node}=[font=\ttfamily\footnotesize]
      \node {$v_0$:courses}
        child {node {$v_1$:course}
          child{node [align=center] {@type \\ \textnormal{``VO''}}}
          child{node [align=center] {$v_2$:lecture}
            child{node {\textnormal{``Algebra I''}}}}
          child{node [align=center] {$v_3$:room}
            child{node [align=center] {\textnormal{``HS1''}}}
            child{node [align=center] {@building \\ \textnormal{``Main''}}}}
        }
        child {node {$v_4$:course}
          child{node [align=center] {@type \\ \textnormal{``UE''}}}
          child{node [align=center] {$v_5$:lecture}
            child{node {\textnormal{``Algebra I''}}}}
          child{node [align=center] {$v_6$:room}
            child{node [align=center] {\textnormal{``SEM1''}}}
            child{node [align=center] {@building \\ \textnormal{``Dep''}}}}
        }
        child {node {$v_7$:course}
          child{node [align=center] {@type \\ \textnormal{``UE''}}}
          child{node [align=center] {$v_8$:lecture}
            child{node {\textnormal{``Economics''}}}}
          child{node [align=center] {$v_9$:room}
            child{node [align=center] {\textnormal{``SEM1''}}}
            child{node [align=center] {@building \\ \textnormal{``Dep''}}}}     
        };
      \end{tikzpicture}
      \caption{The tree representation of the XML document in Figure~\ref{fig:xmlCourse}.}
      \label{fig:treeCourse}
   \end{sidewaysfigure}

\noindent Let $T_1$ and $T_2$ be two XML trees. Then  $T_1$ is subsumed by $T_2$, denoted as $T_1 \preceq T_2$, if $T_2$ contains $T_1$ as a subtree (up to reordering of child nodes). Let $T$ be an XML tree and let $w_1.\cdots.w_n$ be a string, with $w_1,\ldots,w_{n-1} \in El$ and $w_n \in El \cup Att \cup \{ \tS \}$. 
 
   \begin{definition}{(Paths in $T$).} We call $w_1\cdots w_n$ a path in T if there exists vertices $v_1,\ldots,v_n$, such that
     \begin{items}
         \item $v_1 = root$ and $lab(v_1) = w_1$
         \item $v_{i+1}$ is a child of $v_i$ and $lab(v_{i+1}) = w_{i+1}$, for each $i \in [1,n-2]$
         \item If $w_n \in El$, then $v_n$ is a child of $v_{n-1}$ and $lab(v_n) = w_n$
         \item If $w_n = @l$, then $att(v_{n-1},@l)$ is defined
         \item If $w_n = \texttt{S}$, then $v_{n-1}$ has a child in $Str$
      \end{items}
      \noindent $paths(T)$ denotes the set of all paths in T.
   \end{definition}
   
\noindent For example, $\texttt{courses}.\texttt{course}.\texttt{@type}$ and $\texttt{courses}.\texttt{course}.\texttt{room}.S$ are paths in the XML tree of Figure~\ref{fig:treeCourse}. Next, we define the formal model for DTDs.

   \begin{definition}{(DTD \cite{2004arenas})} A Document Type Definition is defined to be $D = (E, A, P, R, r)$, where: 
      \begin{items}
       \item $E \subseteq \mathit{El}$ \ldots finite set of \textit{element types}
       \item $A \subseteq \mathit{Att}$ \ldots finite set of \textit{attributes}
       \item $P$ \ldots a mapping from $E$ to \textit{element type definitions}, i.e. let $\tau \in E$, then $P(\tau) = \tS$ or a regular expression $\alpha$ defining the child elements of $\tau \in E$, where 
       $$\alpha := \epsilon \mid \tau^\prime \mid \alpha|\alpha \mid \alpha, \alpha \mid \alpha^*.$$
       
       The symbol $\epsilon$ denotes the empty sequence; $\tau^\prime$ is an element of $E$; ``$|$'' denotes union, ``$,$'' concatenation and ``$^*$'' the Kleene closure.
       \item $R$ \ldots a mapping from $E$ to the powerset of $A$, i.e. attributes that are available at an element $\tau \in E$.
       \item $r \in E$ \ldots the \textit{element type of the root}\qedhere
      \end{items}
   \label{def:DTD}
   \end{definition}

\noindent The next example shows the translation of the DTD in Figure~\ref{fig:dtdCourse} into the definition given above. Notice that the symbol $\tS$ represents the element type declaration \texttt{\#PCDATA}.
   
\begin{example}
\label{ex:course_dtd}
The DTD in Figure~\ref{fig:dtdCourse} describes the same information as given in Figure~\ref{fig:relCourse}. By Definition~\ref{def:DTD}, we represent the DTD given in Figure~\ref{fig:dtdCourse} as $D_c = (E_{c}, A_{c}, P_{c}, R_{c}, courses)$, where

\begin{itemize}
 \item $E_{c} = \{ courses, course, lecture, room \}$;
 \item $A_{c} = \{ @type, @building \}$;
 \item the mapping $P_{c}$ is defined as:
 \begin{items}
  \item $P_{c}(courses) = course^*$,
  \item $P_{c}(course) = lecture, room$,
  \item $P_{c}(lecture) = \tS$,
  \item $P_{c}(room) = \tS$;
 \end{items}
 \item the mapping $R_{c}$ is defined as:
 \begin{items}
  \item $R_{c}(courses) = \emptyset$,
  \item $R_{c}(course) = \{ @type \}$,
  \item $R_{c}(lecture) = \emptyset$,
  \item $R_{c}(room) = \{ @building \}$.\qedhere
 \end{items}
\end{itemize}
\end{example}

\noindent In order to navigate through an XML tree we introduce the notion of paths in a DTD $D$. 

\begin{definition}{(Paths in $D$)}
A path $w$ is a sequence of elements or attributes, i.e. $$w = w_1 \ldots w_n.$$ A path is in a DTD $D$ if

\begin{items}
         \item $w_1 = r$,
         \item $w_i$ is in the alphabet of $P(w_{i-1})$, for each $i \in [2,n-1]$, and
         \item $w_n$ is in the alphabet of $P(w_{n-1})$ or $w_n = @l$ for some $@l \in R(w_{n-1})$.\qedhere
      \end{items}   
\end{definition}

\noindent The length of a path $w = w_1  \ldots w_n$ is denoted by $length(w) = n$. We denote by $paths(D)$ the set of all paths in a DTD $D$, and with $\ffo{EPaths}(D)$ the set of all paths that end with an element type, rather than an attribute, i.e. $\ffo{EPaths}(D) = \{ p \in paths(D) \mid last(p) \in E\}$, where $last(p) = w_n$. If the set $paths(D)$ is infinite, then we call the DTD $D$ recursive.

\begin{example}
\label{ex:xml_paths}
Let $D_c$ be the DTD introduced in Example~\ref{ex:course_dtd}. Then, the set of paths in $D_c$ is
\begin{align*}
 paths\left(D_c\right) = \{ & courses,  \\
                            & courses.course, \\
                            & courses.course.@type, \\
                            & courses.course.lecture, \\
                            & courses.course.lecture.\tS, \\
                            & courses.course.room, \\
                            & courses.course.room.\tS, \\
                            & courses.course.room.@building \},
\end{align*}
and the set 
\begin{align*}
 \ffo{EPaths}\left(D_c\right) = \{ & courses,  \\
                            & courses.course, \\
                            & courses.course.lecture, \\
                            & courses.course.room \}. \qedhere
\end{align*}
\end{example}

\noindent Since a DTD determines the allowed XML tree, we need to define these. An XML tree $T$ conforms to a DTD $D$, denoted by $T \models D$, if the following holds:

\begin{definition}{($T \models D$ \cite{2004arenas})} Given a DTD $D = (E, A, P, R, r)$ and an XML tree $T = (V, \ffo{lab}, \ffo{ele}, \ffo{att}, root)$, we say that $T$ conforms to $D$ ($T \models D$) if
\begin{itemize}
 \item $\ffo{lab}$ is a mapping from $V$ to $E$.
 \item For each $v \in V$,
 \begin{items}
     \item if $\ffo{ele}(v) = s$, where $s \in Str$, then $P(lab(v)) = \tS$.
     \item if $\ffo{ele}(v) = \left[ v_1, \ldots, v_n \right]$, then the string $\ffo{lab}\left(v_1\right)\cdots\ffo{lab}\left(v_n\right)$ must be in the regular language defined by $P(\ffo{lab}(v))$.
 \end{items}
 \item $\ffo{att}$ is a partial function from $V \times A$ to $Str$, s.t. for any $v \in V$ and $@l \in A$, $\ffo{att}\left(v,@l\right)$ is defined iff $@l \in R(\ffo{lab}(v))$.
 \item $\ffo{lab}\left(root\right) = r$.
\end{itemize}
\end{definition}

\noindent For example, the XML tree shown in Figure~\ref{fig:treeCourse} conforms to the DTD shown in Figure~\ref{fig:dtdCourse}. Additionally, we say that $T$ \textit{is compatible with} $D$, denoted by $T \triangleleft D$, iff $paths(T) \subseteq paths(D)$. Notice that a tree $T$ is compatible with a DTD $D$ if $T$ conforms to $D$ but not vice-versa.
\end{section}

\begin{section}{A Direct-Mapping From Relational Data To XML Documents}
\label{sec:xml_map}

Relational data is easily mapped into XML documents. In this section we introduce the direct-mapping of relational data into XML documents as defined in \cite{2004arenas}. Let $G(A_1, \ldots, A_n)$ be a relational schema. The direct-mapping into an XML representation outputs a DTD. Such a DTD $D_G = (E, A, P, R, db)$ is defined as follows:

\begin{itemize}
 \item $E = \{db,G\}$.
 \item $A = \{@A_1, \ldots, @A_n\}$.
 \item $P(db) = G^*$ and $P(G) = \epsilon$.
 \item $R(db) = \emptyset$ and $R(G) = \{@A_1,\ldots, @A_n\}$.
\end{itemize}

\noindent Notice, that this DTD allows for duplicate representation of tuples (two elements of type $G$ with the same attributes). This is inconsistent with the set semantics of the relational model. After we have introduced data dependencies for DTDs, we will extend this mapping to avoid this problem. Additionally, we also add a translation of FDs to data dependencies in XML. The next example shows the DTD $D_{course}$ translated from the relational schema introduced with Figure~\ref{fig:relCourse}.

\begin{example}
\label{ex:dtdCourseMap}
 The relational schema $course(lecture,type,room,building)$ is mapped into the DTD listed in Figure~\ref{fig:dtdCourseMap}. Notice that this directly-mapped DTD is different from the DTD given in Figure~\ref{fig:dtdCourse}. \end{example}
 
 \begin{figure}[t]
  \centering\begin{lstlisting}[language=DTD]
<!DOCTYPE db [
  <!ELEMENT db (course*)>
  <!ELEMENT course EMPTY>
  <!ATTLIST course
         lecture CDATA #REQUIRED
         type CDATA #REQUIRED
         room CDATA #REQUIRED
         building CDATA #REQUIRED>
]>
\end{lstlisting}
   \caption{A DTD mapped from the relational schema $course$}
   \label{fig:dtdCourseMap}
 \end{figure}
\end{section}

\begin{section}{Data Dependencies}
\label{sec:xml_fd}
In this section we will summarize data dependencies for XML documents, called XML Functional Dependencies (XFDs), introduced in \cite{2004arenas}. First, we need the notion of tree tuples, which gives us a natural representation of XML trees as sets of tuples. This allows us to find a natural definition for FDs in XML documents.
\begin{subsection}{Tree Tuples}
    A tuple in relational databases is a total mapping from the set of attributes to domain values \cite{1995databases}. Tree tuples should extend the notion of relational tuples. Therefore, the function $t$ is called a tree tuple in a DTD $D$, if it assigns to each path in $D$ a value in $\mathit{Vert} \cup \mathit{Str} \cup \{ \bot \}$. Each path in $D$ occurs at most once in $t$. 
    \begin{definition}{(Tree Tuples \cite{2004arenas})}
       \label{def:treetuple}
       Let $D = (E,A,P,R,r)$ be a DTD. A \textit{tree tuple} $t$ in $D$ is a function from $\ffo{paths}\left(D\right)$ to $\mathit{Vert} \cup \mathit{Str} \cup \{ \bot \}$, such that:
       \begin{itemize}
        \item For $p \in \ffo{EPaths}(D)$, $t(p) \in \mathit{Vert} \cup \{ \bot \}$, and $t(r) \neq \bot$.
        \item For $p \in \ffo{paths}(D) - \ffo{EPaths}(D)$, $t(p) \in \mathit{Str} \cup \{ \bot \}$.
        \item If $t(p_1) = t(p_2)$ and $t(p_1) \in \mathit{Vert}$, then $p_1 = p_2$.
        \item If $t(p_1) = \bot$ and $p_1$ is a prefix of $p_2$, then $t(p_2) = \bot$.
        \item $\{ p \in \ffo{paths}(D) \mid t(p) \neq \bot \}$ is finite. \qedhere
       \end{itemize}     
    \end{definition}

    \noindent $\mcT(D)$ denotes the set of all tree tuples in $D$. For a tree tuple $t$ and a path $p$, we write $t.p$ for $t(p)$. Also note that no path $p$ occurs twice in a tree tuple, i.e.\ a tree tuple assigns to every path in $paths(D)$ exactly one value. 
    
   \begin{example}
    \label{ex:treetuple}
    Suppose that $D$ is the DTD shown in Example~\ref{ex:dtdCourse}. Then a tree tuple in $D$ assigns values (taken from the XML tree in Figure~\ref{fig:xmlCourse}) to each path in $paths(D)$ (listed in Example~\ref{ex:xml_paths}):
    
    \begin{align*}
     & t(courses) = v_0 \\
     & t(courses.course) = v_1 \\
     & t(courses.course.@type) = \textnormal{``VO''} \\
     & t(courses.course.lecture) = v_2 \\
     & t(courses.course.lecture.\tS) = \textnormal{``Algebra I''} \\
     & t(courses.course.room) = v_3 \\
     & t(courses.course.room.\tS) = \textnormal{``HS1''} \\
     & t(courses.course.room.@building) = \textnormal{``Main''} \qedhere
    \end{align*}
   \end{example}
   
   \noindent Notice that we only assign to finitely many paths a value different from $\bot$. Thus, even for recursive DTDs, where $paths(D)$ is infinite, we can represent the non-null values of tree tuples as XML trees as follows:
   
   \begin{definition}{($tree_D$ \cite{2004arenas})} 
   Let $D = (E, A, P, R, r)$ be a DTD and let $t$ be a tree tuple, where $t \in \mcT(D)$. The function $tree_D(t)$ outputs an XML tree $(V, lab, ele, att, root)$ as follows: Let $root = t.r$ be the root of this XML tree and
   \begin{itemize}
    \item $V=\{v \in \mathit{Vert} \mid \exists p \in paths(D) \mbox{ such that } v = t.p\}$.
    \item If $v = t.p$ and $v \in V$, then 
    \begin{itemize}
     \item $lab(v) = last(p)$, and
     \item $ele(v)$ is defined to be the list containing $\{t.p^\prime \mid t.p^\prime \neq \bot \mbox{ and } p^\prime = p.\tau, \tau \in E, \mbox{ or } p^\prime = p.\tS\}$, and, since an XML tree must be ordered, this list is ordered lexicographically.
    \end{itemize}
    \item If $v = t.p$, $@l \in A$ and $t.p.@l \neq \bot$, then $att(v,@l) = t.p.@l$. \qedhere
   \end{itemize}
   \end{definition}

   \begin{example}
   \label{ex:tree_D}
   Let $D$ be the DTD from Example~\ref{ex:dtdCourse}, and let $t$ be the tree tuple from Example~\ref{ex:treetuple}. Then, $tree_D(t)$ outputs the XML tree shown in Figure~\ref{fig:tree_D}.
   \end{example}
   
   \begin{figure}[t]
   \centering\begin{tikzpicture}[level distance=12mm,
                       level 1/.style={sibling distance=65mm},
                       level 2/.style={sibling distance=24mm},
                       level 3/.style={sibling distance=15mm},
                       level 4/.style={sibling distance=10mm},
                       edge from parent path={(\tikzparentnode.south) -- (\tikzchildnode.north)}]
      \tikzstyle{every node}=[font=\ttfamily\footnotesize]
      \node {$v_0$:courses}
        child {node {$v_1$:course}
          child{node [align=center] {@type \\ \textnormal{``VO''}}}
          child{node [align=center] {$v_2$:lecture}
            child{node {\textnormal{``Algebra I''}}}}
          child{node [align=center] {$v_3$:room}
            child{node [align=center] {\textnormal{``HS1''}}}
            child{node [align=center] {@building \\ \textnormal{``Main''}}}}
        };
      \end{tikzpicture}
      \caption{The XML tree $tree_D(t)$.}
      \label{fig:tree_D}
   \end{figure}

   \noindent The tree in Figure~\ref{fig:tree_D} conforms to the DTD $D$, which is not necessarily the case in general, since, for example, tree tuples disregard the ordering of child elements. But, by the definition of tree tuples, if $t \in \mcT(D)$ then the XML tree $tree_D(t)$ is compatible with D, i.e.\ $tree_D(t) \triangleleft D$. It is possible to capture the total amount of information in an XML tree with tree tuples. For this, we select only those tree tuples that contain the maximal amount of information. The notion of the maximal amount of information in tree tuples is defined via an ordering (denoted as $\sqsubseteq$) on tuples. Let $t_1$ and $t_2$ be two tree tuples, then $t_1 \sqsubseteq t_2$ if whenever $t_1.p$ is defined, then so is $t_2.p$, and $t_1.p \neq \bot$ implies $t_1.p = t_2.p$ \cite{2004arenas}. We now can define the set of tree tuples of an XML tree $T$.
   
   \begin{definition}{($tuples_D$ \cite{2004arenas})} Given a DTD $D$ and an XML tree $T$ such that $T \triangleleft D$, $tuples_D(T)$ is defined to be the set of maximal, with respect to $\sqsubseteq$, tree tuples $t$ such that $tree_D(t)$ is subsumed by $T$; that is:
   \begin{align*}
    {\max}_\sqsubseteq \{ t\in \mcT(D) \mid tree_D(t) \preceq T \}. & \qedhere
   \end{align*}
   \end{definition}
   
   
   \begin{example}
   \label{ex:tuples}
    In Example~\ref{ex:treetuple} one tree tuple for the DTD in Example~\ref{ex:dtdCourse} was given. The set of tree tuples $tuples_D(T)$ calculated from the tree in Figure~\ref{fig:xmlCourse} is:
    \begin{align*}
     \{ & (v_0,v_1,\textnormal{``VO''},v_2,\textnormal{``Algebra I''},v_3,\textnormal{``HS1''},\textnormal{``Main''}), \\
     & (v_0,v_4,\textnormal{``UE''},v_5,\textnormal{``Algebra I''},v_6,\textnormal{``SEM1''},\textnormal{``Dep''}), \\
     & (v_0,v_7,\textnormal{``UE''},v_8,\textnormal{``Economics''},v_9,\textnormal{``SEM1''},\textnormal{``Dep''}) \} \qedhere
    \end{align*}
   \end{example}
   
   \noindent Notice that the tree tuples in Example~\ref{ex:tuples} resemble the tuples given in the relational table shown in Figure~\ref{fig:relCourse}. This gives evidence that tree tuples are a natural extension of tuples for XML documents. With the direct-mapping of relational data to XML documents introduced in Section~\ref{sec:xml_map} we can establish a one-to-one correspondence between the tuples in an instance $I$ and the tree tuples of the XML tree $T_I$ translated from $I$ \cite{2006arenas2}. With the notion of tree tuples, it is now possible to define functional dependencies for XML.
   \end{subsection}
   
   \begin{subsection}{XML Functional Dependencies}

    In this section we will define FDs for XML documents. Additionally, we inspect the implication problem of such FDs. We also show that FDs for XML documents are not axiomatizable. Last, we give a translation of relational FDs into XML FDs. \\
    
    \noindent For a DTD $D$, an \textit{XML functional dependency} (XFD) over $D$ is an expression of the form $S_1 \ra S_2$, where $S_1$, $S_2$ are finite nonempty subsets of $paths(D)$. The set of all FDs over D is denoted by $\mcFD(D)$. Let $S \subseteq paths(D)$, and let $t, t^\prime \in \mcT(D)$, then $t.S = t^\prime.S$ means $t.p = t^\prime.p$ for all $p\in S$. \\
    
    \noindent Let $D$ be a DTD and let $T$ be an XML tree such that $T \triangleleft D$. Then, $T$ satisfies $S_1 \ra S_2$, denoted as $T \models S_1 \ra S_2$, if for every $t_1$, $t_2 \in tuples_D(T)$, $t_1.S_1 = t_2.S_1$ and $t_1.S_1 \neq \bot$ imply $t_1.S_2 = t_2.S_2$. 
   
   \begin{example}
    \label{ex:XFDs}
    Let $D$ be the DTD introduced in Example~\ref{ex:dtdCourse}. We now want to state XFDs that capture the semantic information of the FDs $\Sigma_{course}$ introduced in Section~\ref{ssec:rel_fd}:
    
    \begin{itemize}
       \item Equation~\ref{eqn:fd_c1} - Each room is associated to a building:
       \begin{align}\texttt{courses}.\texttt{course}.\texttt{room}.\tS \ra \texttt{courses}.\texttt{course}.\texttt{room}.\texttt{@building} \label{eqn:xfd_c1}\end{align}
       \item Equation~\ref{eqn:fd_c2} - A lecture together with its type determine the room they can be held in:
       \begin{align}
	  \{ \texttt{courses}.\texttt{course}.\texttt{lecture}.\tS, \texttt{courses}&.\texttt{course}.\texttt{type}.\tS \} \ra \nonumber \\ & \texttt{courses}.\texttt{course}.\texttt{room}.\tS \label{eqn:xfd_c2}
       \end{align}
       \item Equation~\ref{eqn:fd_c3} - Rooms can only serve lectures of a particular type:
       \begin{align}\texttt{courses}.\texttt{course}.\texttt{room}.\tS \ra \texttt{courses}.\texttt{course}.\texttt{type}.\tS \label{eqn:xfd_c3} \end{align}
   \end{itemize}
   
   \noindent Notice that the XML tree in Figure~\ref{fig:xmlCourse} satisfies all three XFDs. An XML tree $T_\nmodels$ that violates the XFD listed in Equation~\ref{eqn:xfd_c1} is shown in Figure~\ref{fig:xfd_viol}. This is because of the following: \\
   
   \noindent The set $tuples_D(T_\nmodels)$ is:
   \begin{align*}
     \{ & (v_0,v_4,\textnormal{``UE''},v_5,\textnormal{``Algebra I''},v_6,\textnormal{``SEM1''},\textnormal{``Dep''}), \\
     & (v_0,v_7,\textnormal{``UE''},v_8,\textnormal{``Economics''},v_9,\textnormal{``SEM1''},\textnormal{``Main''}) \}.
    \end{align*}
    \noindent Let $t_1$ denote the first tuple from above and $t_2$ the second tuple. Now, 
    $$t_1.\texttt{courses}.\texttt{course}.\texttt{room}.\tS = t_2.\texttt{courses}.\texttt{course}.\texttt{room}.\tS = \textnormal{``SEM1''},$$   
    \noindent but then 
    $$t_1.\texttt{courses}.\texttt{course}.\texttt{@building} = t_2.\texttt{courses}.\texttt{course}.\texttt{@building},$$
    \noindent which is not the case, since $t_1.\texttt{courses}.\texttt{course}.\texttt{@building} = \textnormal{``Dep''}$ and \linebreak $t_2.\texttt{courses}.\texttt{course}.\texttt{@building} = \textnormal{``Main''}$.
   \end{example}
   
   \begin{figure}[t]
\centering\begin{tikzpicture}[level distance=12mm,
                       level 1/.style={sibling distance=65mm},
                       level 2/.style={sibling distance=24mm},
                       level 3/.style={sibling distance=15mm},
                       level 4/.style={sibling distance=10mm},
                       edge from parent path={(\tikzparentnode.south) -- (\tikzchildnode.north)}]
      \tikzstyle{every node}=[font=\ttfamily\footnotesize]
      \node {$v_0$:courses}
        child {node {$v_4$:course}
          child{node [align=center] {@type \\ \textnormal{``UE''}}}
          child{node [align=center] {$v_5$:lecture}
            child{node {\textnormal{``Algebra I''}}}}
          child{node [align=center] {$v_6$:room}
            child{node [align=center] {\textnormal{``SEM1''}}}
            child{node [align=center] {@building \\ \textnormal{``Dep''}}}}
        }
        child {node {$v_7$:course}
          child{node [align=center] {@type \\ \textnormal{``UE''}}}
          child{node [align=center] {$v_8$:lecture}
            child{node {\textnormal{``Economics''}}}}
          child{node [align=center] {$v_9$:room}
            child{node [align=center] {\textnormal{``SEM1''}}}
            child{node [align=center] {@building \\ \textnormal{``Main''}}}}     
        };
      \end{tikzpicture}
      \caption{The XML tree $T_\nmodels$ that violates the XFD given in Equation~\ref{eqn:xfd_c1}.}
      \label{fig:xfd_viol}
   \end{figure}
   
   \noindent As with FDs we define some additional notions. Let $D$ be a DTD, let $\Sigma \subseteq \mcFD(D)$, and let $\varphi \in \mcFD(D)$. A DTD $D$ together with a set of XFDs $\sigma$, denoted by $(D,\Sigma)$, implies $\varphi$, denoted by $(D,\Sigma) \vd \varphi$, if for any tree $T$, with $T \models D$ and $T \models \Sigma$, it is the case that $T \models \varphi$. We denote with $(D,\Sigma)^+$ the set of all XFDs implied by $(D, \Sigma)$. We call an XFD $\varphi$ \textit{trivial} if $(D,\emptyset) \vd \varphi$. For example, let $p \in paths(D)$ and $p.@l \in paths(D)$, then the XFD $p \ra p.@l$ is a trivial.

\begin{subsubsection}{Implication of XFDs}
In this section we summarize the results on the complexity of the implication problem for XFDs. Remember that the implication problem for relational FDs can be decided in linear time (see Section~\ref{sssec:fd_impl}). The implication problem of XFDs is much harder. In principle, checking if an XFD $\varphi$ is not implied by a set of XFDs $\Sigma$, involves the construction of an XML tree, such that $T \models (D, \Sigma)$, but $T \nmodels \varphi$. A proof for the existence of such a tree is a proof for the complement of the implication problem, which is the proof idea of the following theorem:

\begin{theorem}{(Implication Problem for XFDs \cite{2006arenas2})} \label{thm:XFDImpl}\\
The implication problem for XML functional dependencies over DTDs is solvable in \linebreak co-NEXPTIME.
\end{theorem}

\noindent The high complexity is not due to the XFDs, but rather due to the complexity of DTDs. If we restrict the type of DTDs the implication problem can be solved more efficiently. We will give the results established by Arenas and Libkin in \cite{2004arenas, 2006arenas2} for two different types of DTDs.

\begin{paragraph}{Simple DTDs.}
The complexity of DTDs can be restricted through the complexity of the regular expressions in the production rules $P$. For this we define \textit{trivial} regular expressions, which are, given an alphabet $A$, of the form $s_1,\ldots,s_n$, such that for each $s_i$ there is a different letter $a_i \in A$ and $s_i$ is either $a_i$ or $a_i?$ or $a_i^+$ or $a_i^*$. If the words of a regular expression are a permutation of a trivial regular expression, then this regular expression is called \textit{simple}. All production rules in \textit{simple} DTDs use simple regular expressions. Most real world DTDs are of this type \cite{2004arenas}. 

\begin{theorem}{(Implication Problem for XFDs over simple DTDs \cite{2004arenas})} \label{thm:XFDImpl_simple} \\ The implication problem for XFDs over simple DTDs is solvable in quadratic time.\end{theorem}                                                                          
\end{paragraph}

\begin{paragraph}{Relational DTDs.}
The second class of DTDs we introduce are relational DTDs. As we will see, the implication problem for this class is not tractable. A DTD $D$ is called \textit{relational} if for each XML tree $T$, such that $T \models D$, then for any nonempty subset $X$ of $tuples_D(T)$, we can construct a set of trees $\mcT_X$ such that $\mcT_X \models D$. For example, the DTD \texttt{<!ELEMENT a (b,b)>} is not relational \cite{2004arenas}, because the tree built from just one of the tree tuples $\{(v_0,v_1),(v_0,v_2)\}$ does not satisfy the given DTD.

\begin{theorem}{(Implication Problem for XFDs over relational DTDs \cite{2004arenas})} \label{thm:XFDImpl_rel} \\ The implication problem for XFDs over relational DTDs is coNP-complete.\end{theorem}      
\end{paragraph}
\end{subsubsection}

\begin{subsubsection}{Nonaxiomatizability of XFDs}
In Section~\ref{sssec:fd_axiom} we gave an axiomatic system for relational FDs. Unfortunately, it is not possible to give an axiomatization for XFDs. First, we introduce some additional terms. Let $D$ be a DTD and let $\Sigma$ be a set of XFDs over D. $(D, \Sigma)$ is \textit{closed under implication} if for every $\varphi$ over $D$ such that $(D, \Sigma) \vd \varphi$, then $\varphi \in \Sigma$. Moreover, $(D, \Sigma)$ is \textit{closed under k-ary implication} if  for every $\varphi$ over $D$, if there exists $\Sigma^\prime \subseteq \Sigma$ such that $|\Sigma^\prime|\leq k$ and $(D, \Sigma^\prime) \vd \varphi$, it is the case that $\varphi \in \Sigma$ \cite{2004arenas}.
An axiomatization contains rules of the form \textit{if} $\Gamma$ \textit{then} $\gamma$, where $\Gamma$ and $\gamma$ are FDs. Let $k$ be an integer. If $|\Gamma| \leq k$, for any $\Gamma$ that appears in the left-hand side of a rule, then we say that this set of rules is a $k$-ary axiomatization. The next proposition gives a necessary condition for the existence of a $k$-ary axiomatization.

A proof for the contrapositive of the next proposition, altered for XFDs, shows that the implication problem for XFDs does not admit a finite axiomatization.

\begin{proposition}{(Proposition 7.5 of \cite{2004arenas})}\label{prop:kaxiom} For every $k \geq 0$, if there is a k-ary ground axiomatization for the implication problem of XFDs, then for every DTD $D$ and a set of XFDs over $\Sigma$ over $D$, if $(D, \Sigma)$ is closed under $k$-ary implication then $(D, \Sigma)$ is closed under implication.
\end{proposition}

\noindent This proposition was already proven in \cite{1995databases}. If we now want to show that there is no axiomatic system for XFDs, we use Proposition~\ref{prop:kaxiom} and show that the necessary conditions for a $k$-axiomatic system are not fulfilled. This can be done by finding a DTD $D$ and a set of functional dependencies $\Sigma$, which have the following properties:

\begin{itemize}
 \item $(D,\Sigma)$ is closed under k-ary implication, and
 \item $(D,\Sigma)$ is not closed under implication.
\end{itemize}

\noindent Arenas and Libkin use this idea in order to establish a proof for the next theorem.

\begin{theorem}{(Nonaxiomatizability of XFDs)} \\
The implication problem for XML functional dependencies is not finitely axiomatizable.
\end{theorem}
\end{subsubsection}
   
\begin{subsubsection}{The Direct-Mapping of XFDs}
We will now extend the direct mapping introduced in Section~\ref{sec:xml_map} with the translation of FDs into XFDs. Let $\FD$ be a set of FDs over the schema $G(A_1,\ldots,A_n)$, such that, without loss of generality, all FDs are of the form $X \ra A$, where $A$ is an attribute. Then the set $\Sigma_\FD$ of XFDs is defined as follows \cite{2004arenas}:
\begin{itemize}
 \item For each FD $A_{i_1}, \ldots, A_{i_m} \ra A_i \in FD$, 
    $$\{db.G.@A_{i_1},\ldots,db.G.@A_{i_m}\} \ra db.G.@A_i \in \Sigma_\FD.$$
 \item Additionally, to avoid duplicates,  
    $$\{db.G.@A_1, \ldots, db.G.@A_n\} \ra db.G \in \Sigma_\FD.$$
\end{itemize}

\begin{definition}{(Direct-Mapping of XFDs)} \\
Let $(G,\FD)$ be a relational schema, then the direct-mapping to XML FDs is $(D_G,\Sigma_\FD)$ as previously defined.
\end{definition}


\begin{example}
We extend Example~\ref{ex:dtdCourseMap} to include the FDs given in Equations~\ref{eqn:fd_c1}-\ref{eqn:fd_c3}. The set $\Sigma_{\Sigma_{course}}$ of XFDs is defined as:

       \begin{align}\texttt{db}.\texttt{courses}.\texttt{@room} \ra \texttt{db}.\texttt{courses}.\texttt{@building} \label{eqn:xfd_c1_map} \end{align}
       \begin{align}
	   \{ \texttt{db}.\texttt{courses}.\texttt{@lecture}, \texttt{db}.\texttt{courses}.\texttt{@type} \} \ra  \texttt{db}.\texttt{courses}.\texttt{@room} \label{eqn:xfd_c2_map} 
       \end{align}
       \begin{align}
       \texttt{db}.\texttt{courses}.\texttt{@room} \ra \texttt{db}.\texttt{courses}.\texttt{@type} \label{eqn:xfd_c3_map} 
       \end{align}
       \begin{align}
       \{ & \texttt{db}.\texttt{courses}.\texttt{@lecture}, \texttt{db}.\texttt{courses}.\texttt{@type}, \nonumber \\
          & \texttt{db}.\texttt{courses}.\texttt{@room}, \texttt{db}.\texttt{courses}.\texttt{@building} \} \ra  \texttt{db}.\texttt{courses} \label{eqn:xfd_map} 
       \end{align}\qedhere
\end{example}


\end{subsubsection}

\end{subsection}

\end{section}

\begin{section}{Normal Forms}
\label{sec:xml_nf}

So far we have established the preliminaries to define a normal form for XML documents. In general, the goal is to generalize BCNF, which says that we should not represent the same fact twice. Therefore, we will first look at what a ``redundancy'' is in the context of XML documents and then, based on those insights, study XML Normal Form as defined in \cite{2004arenas}.

\begin{subsection}{Redundancy in XML Documents}
Let us consider the XML tree given in Figure~\ref{fig:treeCourse}. Each room has a name and is located in a specific building. Suppose a new course is added to this XML document. This course is also located in the seminar room ``SEM1''. Then, because of the XFD in Equation~\ref{eqn:xfd_c1}, we have to store the associated building ``Dep'' twice in this XML tree. Thus, the DTD together with the XFD in Equation~\ref{eqn:xfd_c1} leads to redundancy. Such a redundancy is closely related to redundancies in relational data and can also be repaired in such a manner. We create new elements that store the rooms together with their building attribute. The lecture now just stores a reference to the room element. The resulting XML tree is illustrated in Figure~\ref{fig:treeCourseRoom}. The next example illustrates a redundancy more closely related to the hierarchical structure of XML documents.

\begin{sidewaysfigure}[htbp]
\centering\begin{tikzpicture}[level distance=12mm,
                       level 1/.style={sibling distance=42mm},
                       level 2/.style={sibling distance=16mm},
                       level 3/.style={sibling distance=10mm},
                       level 4/.style={sibling distance=10mm},
                       edge from parent path={(\tikzparentnode.south) -- (\tikzchildnode.north)}]
      \tikzstyle{every node}=[font=\ttfamily\footnotesize]
      \node {$v_0$:courses}
        child {node {$v_1$:course}
          child{node [align=center] {@type \\ \textnormal{``VO''}}}
          child{node [align=center] {$v_2$:lecture}
            child{node {\textnormal{``Algebra I''}}}}
          child{node [align=center] {$v_3$:loc}
            child{node [align=center] {\textnormal{``HS1''}}}}
        }
        child {node {$v_4$:course}
          child{node [align=center] {@type \\ \textnormal{``UE''}}}
          child{node [align=center] {$v_5$:lecture}
            child{node {\textnormal{``Algebra I''}}}}
          child{node [align=center] {$v_6$:loc}
            child{node [align=center] {\textnormal{``SEM1''}}}}
        }
        child {node {$v_7$:course}
          child{node [align=center] {@type \\ \textnormal{``UE''}}}
          child{node [align=center] {$v_8$:lecture}
            child{node {\textnormal{``Economics''}}}}
          child{node [align=center] {$v_9$:loc}
            child{node [align=center] {\textnormal{``SEM1''}}}}
        }
        child {node {$v_{10}$:room}
            child{node [align=center] {\textnormal{``HS1''}}}
            child{node [align=center] {@building \\ \textnormal{``Main''}}}
        }
        child {node {$v_{11}$:room}
            child{node [align=center] {\textnormal{``SEM1''}}}
            child{node [align=center] {@building \\ \textnormal{``Dep''}}}
        };
      \end{tikzpicture}
      \caption{The tree representation of the XML document in Figure~\ref{fig:treeCourse} with a new element room, that removes a redundancy.}
      \label{fig:treeCourseRoom}
   \end{sidewaysfigure}

   \begin{figure}[t]
  \centering\begin{lstlisting}[language=DTD]
<!DOCTYPE db [
  <!ELEMENT db (conf*)>
  <!ELEMENT conf (title, issue+)>
  <!ELEMENT title (#PCDATA)>
  <!ELEMENT issue (inproceedings+)>
  <!ELEMENT inproceedings (author+, title)>
    <!ATTLIST inproceedings
              key ID #REQUIRED
              pages CDATA #REQUIRED
              year CDATA #REQUIRED>
  <!ELEMENT author (#PCDATA)>
]>
\end{lstlisting}
   \caption{Part of the DTD from the DBLP database \cite{2003ley}, taken from \cite{2004arenas}}
   \label{fig:dtdConf}
 \end{figure}
   
\begin{example}{(Example 1.2 from \cite{2004arenas})}
\label{ex:dtdConf}
The DTD in Figure~\ref{fig:dtdConf} is a part of the DBLP database \cite{2003ley} and stores data about conferences. In particular, this DTD stores the information of papers, which appeared in conference proceedings. Conference proceedings are in general distributed into several \texttt{issues}. Each issue contains several papers, stored in \texttt{inproceedings} elements. Those have a \texttt{@year} attribute. Now consider the following XFD, which says that any two \texttt{inproceedings} children of the same \texttt{issue} must have the same year:

\begin{align}
\texttt{db}.\texttt{conf}.\texttt{issue} \ra \texttt{db}.\texttt{conf}.\texttt{issue}.\texttt{inproceedings}.\texttt{@year}. \label{eqn:XFD_conf} 
\end{align}

\noindent This XFD leads to a redundancy. The \texttt{@year} attribute is stored several times per issue. This can be easily repaired by moving the \texttt{@year} attribute to the \texttt{issue} element. 
\end{example}
 

\end{subsection}

\begin{subsection}{XML Normal Form}
 XML Normal Form (XNF) generalizes BCNF for XML documents \cite{2004arenas}. Thus, it tries to avoid redundancies as described in the previous section. We need to express that we do not want to store implied data several times in an XML tree. This is captured by the following definition:
 
 \begin{definition}{(XML Normal Form \cite{2004arenas})}
   Given a DTD $D$ and a set $\Sigma \subseteq \mcFD(D)$ of XFDs over $D$, $(D,\Sigma)$ is in XML Normal Form (XNF) iff for every nontrivial XFD $\varphi \in (D,\Sigma)^+$, of the form $S\ra p.@l$ or $S \ra p.S$, it is the case that $S \ra p$ is in $(D,\Sigma)^+$.
   \end{definition}
   
\noindent Intuitively, this definition says that for all trees $T$ conforming to a DTD $D$, whenever some set of paths $S$ determines an attribute $@l$ of an element $p$, this attribute should only be stored once at exactly this element $p$. It is important that we only consider nontrivial XFDs, because the trivial FD $p.@l \ra p.@l$ is always in $(D,\Sigma)^+$, but often $p.@l \ra p \notin (D,\Sigma)^+$. We will now revisit the examples of the previous section.

\begin{example}
Let us first consider the DTD given in Figure~\ref{fig:dtdConf} together with the XFD given in Equation
\ref{eqn:XFD_conf}. This DTD is not in XNF, because the XFD
\begin{align}
   \texttt{db}.\texttt{conf}.\texttt{issue} \ra \texttt{db}.\texttt{conf}.\texttt{issue}.\texttt{inproceedings} \label{eqn:XFD_conf_XNF}
\end{align}
\noindent is not in $(D, \Sigma)^+$. The above XFD would imply that each \texttt{issue} element has only one \texttt{inproceedings} child element. The DTD, resulting from repair proposed in Example~\ref{ex:dtdConf}, is in XNF. During the repair, the XFD from Equation~\ref{eqn:XFD_conf} is not altered but dropped, since $\texttt{db}.\texttt{conf}.\texttt{issue} \ra \texttt{db}.\texttt{conf}.\texttt{issue}.\texttt{@year}$ is a trivial XFD.
\end{example}

\begin{example}
\label{ex:XNFcourse}
We consider the DTD in Figure~\ref{fig:dtdCourseMap}, which is translated from the relational schema given in Figure~\ref{fig:relCourse}. The translated XFDs $\Sigma_{\Sigma_{course}}$ are listed in Equations~\ref{eqn:xfd_c1_map}-\ref{eqn:xfd_map}. The DTD together with its XFDs is not in XNF. There are two XNF violations:

\begin{itemize}
 \item First, consider the XFD in Equation~\ref{eqn:xfd_c1_map}. The XFD $\texttt{db}.\texttt{courses}.\texttt{@room} \ra$ \linebreak  $\texttt{db}.\texttt{courses}$ is not in $(D_{course},\Sigma_{\Sigma_{course}})^+$, which would imply that two different courses cannot be in the same room. If we store the rooms and their building separately, as illustrated in Figure~\ref{fig:treeCourseRoom}, the XFD in Equation~\ref{eqn:xfd_c1_map} no longer violates XNF. 
 \item Additionally, also the XFD in Equation~\ref{eqn:xfd_c3_map} leads to an XNF violation, because the XFD $\texttt{db}.\texttt{courses}.\texttt{@room} \ra \texttt{db}.\texttt{courses}$ is not in $(D_{course},\Sigma_{\Sigma_{course}})^+$. Notice that the original FD of the relational schema also leads to a BCNF violation.
\end{itemize}

\noindent As we have seen in Example~\ref{ex:BCNF}, a repair of the corresponding relational schema changes the FDs, since $lecture,type \ra room$ cannot be stated any longer. In XML we can use the hierarchical structure of XML documents to achieve a DTD that keeps all XFDs \cite{2006arenas}. Such a DTD $D_\mathit{XNF}$, generated by the approach proposed in \cite{2005kolahi}, is listed in Figure~\ref{fig:dtdCourseXNF}. 

\begin{figure}[t]
  \centering\begin{lstlisting}[language=DTD]
<!DOCTYPE db [
  <!ELEMENT db (t*,r*)>
  <!ELEMENT t (l*)>
  <!ATTLIST t
         type CDATA #REQUIRED>
  <!ELEMENT l (loc*)>
  <!ATTLIST l
         lecture CDATA #REQUIRED>
  <!ELEMENT loc EMPTY>
  <!ATTLIST loc
         room CDATA #REQUIRED>
  <!ELEMENT rooms EMPTY>
  <!ATTLIST rooms
         room CDATA #REQUIRED
         building CDATA #REQUIRED>
]>
\end{lstlisting}
   \caption{A DTD originally mapped from the relational schema $course$, which is repaired to be in XNF}
   \label{fig:dtdCourseXNF}
 \end{figure}

\newpage

\noindent Let $\Sigma_\mathit{XNF}$ be the following XFDs over $D_\mathit{XNF}$:
\begin{align}
   \texttt{db}.\texttt{t}.\texttt{@type} & \ra \texttt{db}.\texttt{t} \label{eqn:xnf_1} \\
   \{ \texttt{db}.\texttt{t}, \texttt{db}.\texttt{t}.\texttt{l}.\texttt{@lecture} \} & \ra \texttt{db}.\texttt{t}.\texttt{l} \label{eqn:xnf_2} \\
   \{ \texttt{db}.\texttt{t}.\texttt{l}, \texttt{db}.\texttt{t}.\texttt{l}.\texttt{loc}.\texttt{@room} \} & \ra \texttt{db}.\texttt{t}.\texttt{l}.\texttt{loc} \label{eqn:xnf_3} \\
   \{ \texttt{db}.\texttt{t}.\texttt{l}.\texttt{@lecture}, \texttt{db}.\texttt{t}.\texttt{@type} \} & \ra \texttt{db}.\texttt{t}.\texttt{l}.\texttt{loc}.\texttt{@room}  \label{eqn:xnf_4} \\
   \texttt{db}.\texttt{t}.\texttt{l}.\texttt{loc}.\texttt{@room} & \ra \texttt{db}.\texttt{t}.\texttt{@type} \label{eqn:xnf_5} \\
   \texttt{db}.\texttt{rooms}.\texttt{@room} & \ra \texttt{db}.\texttt{rooms} \label{eqn:xnf_6} \\
   \texttt{db}.\texttt{rooms}.\texttt{@room} & \ra \texttt{db}.\texttt{rooms}.\texttt{@building}  \label{eqn:xnf_7}
\end{align}

\noindent The idea of the DTD $D_\mathit{XNF}$ together with the XFDs $\Sigma_\mathit{XNF}$ is to first group together all courses of a particular type (see Equation~\ref{eqn:xnf_1}). Then, we store the different lecture names with their locations (Equations~\ref{eqn:xnf_2} and~\ref{eqn:xnf_3}). Equations~\ref{eqn:xnf_4} and~\ref{eqn:xnf_5} correspond to the original FDs $lecture,type \ra room$ and $room \ra type$, respectively. Equation~\ref{eqn:xnf_5} enforces that the same room cannot appear in different $\texttt{t}$ subtrees. Finally, Equations~\ref{eqn:xnf_6} and~\ref{eqn:xnf_7} store that a room is located in a specific building.\\

\noindent It can be easily verified that the XFDs $\{ \texttt{db}.\texttt{t}.\texttt{l}.\texttt{@lecture}, \texttt{db}.\texttt{t}.\texttt{@type} \} \ra \texttt{db}.\texttt{t}.\texttt{l}.\texttt{loc}$, $\texttt{db}.\texttt{t}.\texttt{l}.\texttt{loc}.\texttt{@room} \ra \texttt{db}.\texttt{t}$ and $\texttt{db}.\texttt{rooms}.\texttt{@room} \ra \texttt{db}.\texttt{rooms}$ are in $(D_\mathit{XNF},\Sigma_\mathit{XNF})^+$. Therefore $(D_\mathit{XNF},\Sigma_\mathit{XNF})$ is in XNF. The redundancy-free XML tree with the same information as in Figure~\ref{fig:relCourse} is illustrated in Figure~\ref{fig:XNFcourse}.\end{example}

\begin{sidewaysfigure}[htbp]
\centering\begin{tikzpicture}[level distance=12mm,
                       edge from parent path={(\tikzparentnode.south) -- (\tikzchildnode.north)}]
      \tikzstyle{every node}=[font=\ttfamily\footnotesize,align=center]
      \Tree [ .$v_0$ [ .$v_1$:t @type\\\textnormal{``VO''} [ .$v_2$:l @lecture\\\textnormal{``Algebra I''} [ .$v_3$:loc @room\\\textnormal{``HS1''} ] ]
                     ]
                     [ .$v_4$:t @type\\\textnormal{``UE''} [ .$v_5$:l @lecture\\\textnormal{``Algebra I''} [ .$v_6$:loc @room\\\textnormal{``SEM1''} ] ]
                                                           [ .$v_7$:l @lecture\\\textnormal{``Economics''} [ .$v_8$:loc @room\\\textnormal{``SEM1''} ] ]
                     ]
                     [ .$v_9$:rooms @room\\\textnormal{``HS1''} @building\\\textnormal{``Main''} ]
                     [ .$v_10$:rooms @room\\\textnormal{``SEM1''} @building\\\textnormal{``Dep''} ]
            ]
      \end{tikzpicture}
      \caption{A redundancy free XML tree with the same information as in Figure~\ref{fig:relCourse}.}
      \label{fig:XNFcourse}
   \end{sidewaysfigure}   
   
\clearpage   
 
\noindent The next theorem shows that BCNF and XNF are equivalent.

\begin{theorem}{(BCNF and XNF, Proposition 5.5 of \cite{2004arenas})}
Let $G(A_1,\ldots,A_n)$ be a relational schema, $\FD$ be a set of functional dependencies over $G$. $D_G$ is the DTD and $\Sigma_\FD$ is the set of XFDs, which are translated by the direct-mapping of relational schemas to XML.  Then, $(G,\FD)$ is in BCNF iff $(D_G,\Sigma_\FD)$ is in XNF.
\end{theorem}

\begin{proof}
The proof can be found in \cite{2004arenas}. It follows from the fact that we can encode nested relation schemas into XML trees and that a normal form for nested relation schemas (NNF-FD) \cite{1996mok} coincides with XNF \cite{2004arenas}. 
\end{proof}


\begin{paragraph}{The Complexity of Testing XNF.} By definition, testing XNF involves checking a condition on all XFDs implied by a DTD $D$ and a set of XFDs $\Sigma$. Since $\Sigma$ contains a finite number of paths, we can restrict every recursive DTD to a finite number of ``unfoldings'' of recursive rules \cite{2006arenas}. Therefore it is possible to assume, without loss of generality, that DTDs are non-recursive. Then, we know that testing XNF is decidable. This follows from Theorem~\ref{thm:XFDImpl}. If we restrict the class of DTDs we can first prove the following property.

\begin{proposition}{\cite{2004arenas}} Given a relational DTD $D$ and a set $\Sigma$ of XFDs over $D$, then $(D, \Sigma)$ is in XNF iff for each nontrivial XFD of the form $S \ra p.@l$ or $S \ra p.\tS$ in $\Sigma$, $S \ra p \in (D,\Sigma)^+$.
\end{proposition}

\noindent This proposition restricts the number of XFDs we have to check. Together with the complexity of the implication problem of simple and relational DTDs (see Theorems~\ref{thm:XFDImpl_simple} and~\ref{thm:XFDImpl_rel} respectively) the following follows:

\begin{corollary}
{\cite{2004arenas}} Testing if $(D, \Sigma)$ is in XNF can be done in cubic time for simple DTDs, and is coNP-complete for relational DTDs.
\end{corollary}
\end{paragraph}
\end{subsection}
\end{section}

\begin{section}{Summary}
In this chapter we have introduced a normal form for XML documents. First, we presented a formal model for XML documents. We used DTDs to define the structure of an XML document. We showed that we can directly map relational schemas to DTDs and relational instances to XML documents. The information containted in an XML document can be represented using tree tuples. XML functional dependencies formulated over DTDs are evaluated over tree tuples. We can translate FDs over a relational schema to XFDs over a DTD, that is generated through the direct mapping from the relational schema. Such XFDs capture the semantic information of the original FDs. The implication problem for arbitrary DTDs is in co-NEXPTIME, in quadratic time for simple DTDs and coNP-complete for relational DTDs. Furthermore, we have shown that XFDs are nonaxiomatizable. \\

\noindent XFDs lead to redundancies in XML documents. A DTD in XML normal form tries to avoid redundancies. A DTD is in XNF if for every element $e$ in an XML document that is implied by some other elements $X$ it is the case that also the parent element of $e$ is implied by the elements $X$. This generalizes the idea that these elements $X$ must be a superkey. We have shown that a schema together with a set of FDs is in BCNF if and only if the DTD and a set of XFDs, both generated by the direct-mapping from the relational schema and FDs, is in XNF. This result shows that XNF is a generalization of BCNF. For relational it is possible to show that XNF testing is coNP-complete and for simple DTDs it can be done in cubic time.
\end{section}
